//
//  Lesson1.swift
//  AlgorithmSwift
//
//  Created by 李笑臣 on 2020/10/9.
//

import Cocoa

/**
 
 1. 两数之和
 
 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 
 示例:

 给定 nums = [2, 7, 11, 15], target = 9

 因为 nums[0] + nums[1] = 2 + 7 = 9
 所以返回 [0, 1]
 
 */

class Lesson1: NSObject {
    
    
    class func run() -> Void {
        
        // 准备参数
        let times = 2000
        
        var nums: Array<Int> = []
        for x in 0 ..< times {
            nums.append(x)
        }
        nums.sort { (x, y) -> Bool in
            // 0到9
            let random = arc4random() % 10
            if random <= 4 {
                return true
            }
            else {
                return false
            }
        }
        nums.insert(times * 10, at: times / 2)
        let target = times * 10 + times / 2
        
        // 计算时间参数
        var startTime: Double
        var endTime: Double
        var timeString: String
        
        
        // 开始计算
        // 1
        startTime = CFAbsoluteTimeGetCurrent()
        
        reason1(withNums: nums, target: target)
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
        
        // 2
        startTime = CFAbsoluteTimeGetCurrent()
        
        reason2(withNums: nums, target: target)
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
        
        // 3
        startTime = CFAbsoluteTimeGetCurrent()
        
        reason3(withNums: nums, target: target)
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
        
        // 4
        startTime = CFAbsoluteTimeGetCurrent()
        
        reason4(withNums: nums, target: target)
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
        
        // 5
        startTime = CFAbsoluteTimeGetCurrent()
        
        reason5(withNums: nums, target: target)
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
    }
    
    // 最初版本
    class func reason1(withNums nums: Array<Int>, target: Int) -> Void {
        
        for (index1, num1) in nums.enumerated() {
            for (index2, num2) in nums.enumerated() {
                if index1 != index2 && num1 + num2 == target {
                    debugPrint("两下标为： \(index1) 和 \(index2)")
                    return
                }
            }
        }
    }
    
    // 点击量很高的基本方法
    class func reason2(withNums nums: Array<Int>, target: Int) -> Void {
        
        for (index1, num1) in nums.enumerated() {
            for index2 in (index1 + 1) ..< nums.count {
                if index1 != index2 && num1 + nums[index2] == target {
                    debugPrint("两下标为： \(index1) 和 \(index2)")
                    return
                }
            }
        }
    }
    
    // 没用版本
    class func reason3(withNums nums: Array<Int>, target: Int) -> Void {
        
        for (index1, num1) in nums.enumerated() {
            for (index2, num2) in nums.enumerated() {
                if index1 < index2 && num1 + num2 == target {
                    debugPrint("两下标为： \(index1) 和 \(index2)")
                    return
                }
            }
        }
    }
    
    // 没什么用版本
    class func reason4(withNums nums: Array<Int>, target: Int) -> Void {
        
        for (index1, num1) in nums.prefix(nums.count - 1).enumerated() {
            let nextIndex = index1 + 1
            for (index2, num2) in nums.suffix(from: nextIndex).enumerated() {
                if index1 != index2 && num1 + num2 == target {
                    debugPrint("两下标为： \(index1) 和 \(index2 + nextIndex)")
                    return
                }
            }
        }
    }
    
    // 系统方法之 firstIndex (性能不够好)
    class func reason5(withNums nums: Array<Int>, target: Int) -> Void {
        
        for (index1, num) in nums.enumerated() {
            let dif = target - num
            if nums.contains(dif) {
                let index2 = nums.firstIndex(of: dif)!
                debugPrint("两下标为： \(index1) 和 \(index2)")
                return
            }
        }
    }
    
    // 网上学来的，用一个Dictionary，key为差值，value为下标
    class func reason6(withNums nums: Array<Int>, target: Int) -> Void {
        
        for (index1, num) in nums.enumerated() {
            let dif = target - num
            if nums.contains(dif) {
                let index2 = nums.firstIndex(of: dif)!
                debugPrint("两下标为： \(index1) 和 \(index2)")
                return
            }
        }
    }
}
